package com.lw.leetcode.sort.b;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 2208. 将数组和减半的最少操作次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/21 13:48
 */
public class HalveArray {

    public int halveArray(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return 1;
        }
        PriorityQueue<Double> pq = new PriorityQueue<>((a, b) -> Double.compare(b, a));
        double sum = 0D;
        for (int num : nums) {
            sum += num;
            pq.add((double) num);
        }
        sum /= 2;
        int count = 0;
        double decr = 0D;
        while (decr < sum) {
            double poll = pq.poll();
            decr += poll / 2;
            pq.add(poll / 2);
            count++;
        }
        return count;
    }

}
